{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Subgraph Extraction\n",
    "\n",
    "In this notebook, we will use cuGraph to extract a subgraph from the test graph.  \n",
    "\n",
    "Notebook Credits\n",
    "* Original Authors: Bradley Rees\n",
    "* Created:   10/16/2019\n",
    "* Last Edit: 03/03/2020\n",
    "\n",
    "RAPIDS Versions: 0.13\n",
    "\n",
    "Test Hardware\n",
    "* GV100 32G, CUDA 10.2\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction\n",
    "\n",
    "Subgraph Extraction allows the extraction of a portion of a graph and returned as a Graph object that follow-on analytics can be applied against.  For example, many of the community detection analytics simply return a list of vertices in a cluster.  In order to run follow-on processing against a cluster, all the edges within that cluster are also needed.  \n",
    "\n",
    "For this notebook, we will run Louvain to determine the clusters and then extract one of the clusters using Subgraph Extraction.  We will then explore that extracted subgraph.  \n",
    "\n",
    "\n",
    "\n",
    "To compute the Louvain cluster in cuGraph use: <br>\n",
    "* __G', df = cugraph.subgraph(G, v)__\n",
    "    * G: A cugraph.Graph object\n",
    "    * v: cudf.Series - list of vertex IDs to be extracted\n",
    "\n",
    "Returns:<br>\n",
    "* G': A cugraph.Graph object\n",
    "* df: cudf.DataFrame\n",
    "    * old - the original vertex ID\n",
    "    * new - the new renumbered vertex ID\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Notice\n",
    "Subgraph Extraction is currently not fully functional.  There are two outstanding issues to address the problems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## cuGraph Notice \n",
    "The current version of cuGraph has some limitations:\n",
    "\n",
    "* Vertex IDs need to be 32-bit integers.\n",
    "* Vertex IDs are expected to be contiguous integers starting from 0.\n",
    "\n",
    "cuGraph provides the renumber function to mitigate this problem. Input vertex IDs for the renumber function can be either 32-bit or 64-bit integers, can be non-contiguous, and can start from an arbitrary number. The renumber function maps the provided input vertex IDs to 32-bit contiguous integers starting from 0. cuGraph still requires the renumbered vertex IDs to be representable in 32-bit integers. These limitations are being addressed and will be fixed soon.    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Test Data\n",
    "We will be using the Zachary Karate club dataset \n",
    "*W. W. Zachary, An information flow model for conflict and fission in small groups, Journal of\n",
    "Anthropological Research 33, 452-473 (1977).*\n",
    "\n",
    "\n",
    "![Karate Club](../img/zachary_black_lines.png)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Prep"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import needed libraries\n",
    "import cugraph\n",
    "import cudf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Read data using cuDF"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test file    \n",
    "datafile='../data//karate-data.csv'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# read the data using cuDF\n",
    "gdf = cudf.read_csv(datafile, delimiter='\\t', names=['src', 'dst'], dtype=['int32', 'int32'] )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Run Louvain to find a cluster to extract\n",
    "Since the focus is on the subgraph extraction portion, we are going to leave the vertex IDs are they are and just accept that there is an extract cluster in the reults with vertex 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# The louvain algorithm requires that there are vertex weights.  Just use 1.0 \n",
    "gdf[\"data\"] = 1.0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create a Graph \n",
    "G = cugraph.Graph()\n",
    "G.from_cudf_edgelist(gdf, source='src', destination='dst', edge_attr='data')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Call Louvain on the graph\n",
    "df, mod = cugraph.louvain(G) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# How many partitions where found\n",
    "part_ids = df[\"partition\"].unique()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 partition detected\n"
     ]
    }
   ],
   "source": [
    "print(str(len(part_ids)) + \" partition detected\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Partition 0:\n",
      "[1, 2, 3, 4, 8, 10, 12, 13, 14, 18, 20, 22]\n",
      "Partition 1:\n",
      "[5, 6, 7, 11, 17]\n",
      "Partition 2:\n",
      "[9, 15, 16, 19, 21, 23, 27, 29, 30, 31, 32, 33, 34]\n",
      "Partition 3:\n",
      "[24, 25, 26, 28]\n"
     ]
    }
   ],
   "source": [
    "for p in range(len(part_ids)):\n",
    "    part = []\n",
    "    for i in range(len(df)):\n",
    "        if (df['partition'][i] == p):\n",
    "            part.append(df['vertex'][i])\n",
    "    print(\"Partition \" + str(p) + \":\")\n",
    "    print(part)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Run Subgraph Extraction\n",
    "Let's extract cluster 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "vids = df.query(\"partition == 1\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "v = cudf.Series(vids['vertex'])\n",
    "len(v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "subG = cugraph.subgraph(G, v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Main Graph\n",
      "\tNumber of Vertices: 34\n",
      "\tNumber of Edges:    156\n"
     ]
    }
   ],
   "source": [
    "print(\"Main Graph\")\n",
    "print(\"\\tNumber of Vertices: \" + str(G.number_of_vertices()))\n",
    "print(\"\\tNumber of Edges:    \" + str(G.number_of_edges()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Subgraph\n",
      "\tNumber of Vertices: 5\n",
      "\tNumber of Edges:    12\n"
     ]
    }
   ],
   "source": [
    "print(\"Subgraph\")\n",
    "print(\"\\tNumber of Vertices: \" + str(subG.number_of_vertices()))\n",
    "print(\"\\tNumber of Edges:    \" + str(subG.number_of_edges()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "coo = cudf.DataFrame()\n",
    "subDF = subG.view_edge_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(subDF)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "___\n",
    "Copyright (c) 2019, NVIDIA CORPORATION.\n",
    "\n",
    "Licensed under the Apache License, Version 2.0 (the \"License\");  you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0\n",
    "\n",
    "Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an \"AS IS\" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.\n",
    "___"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "cugraph_dev",
   "language": "python",
   "name": "cugraph_dev"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
